home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Cream of the Crop 1
/
Cream of the Crop 1.iso
/
UTILITY
/
FSULTRA1.ARJ
/
ULTRA.DOC
< prev
next >
Wrap
Text File
|
1992-06-18
|
11KB
|
261 lines
FSU - ULTRA The greatest random number generator that ever was
or ever will be. Way beyond Super-Duper.
(Just kidding, but we think its a good one.)
Authors: Arif Zaman (arif@stat.fsu.edu) and
George Marsaglia (geo@stat.fsu.edu).
Date: 27 May 1992
Version: 1.05
Copyright: To obtain permission to incorporate this program into
any commercial product, please contact the authors at
the e-mail address given above or at
Department of Statistics and
Supercomputer Computations Research Institute
Florida State University
Tallahassee, FL 32306.
See Also: README for a brief description
ULTRA.DOC for a detailed description
-----------------------------------------------------------------------
DETAILED DESCRIPTION:
This is an implementation (in C and in PC assembler) of a random number
generator with many good properties that common generators lack, namely:
HIGH QUALITY
o Extremely long period (more than 10^356---that's more than
10^270 numbers for each atom in the universe, in case you
want to simulate creation).
o Combines two different types of generators, to achieve a very
thorough mixing.
o All possible values of 37 consecutive numbers occur with the
correct frequencies in the long run.
o Single precision reals (by far the most common) are guaranteed
to have full precision in the fraction (mantissa).
Almost all generators produce reals by dividing a 32 (or 31) bit
integer by 2^32 (2^31). This means the smallest possible
random reals are small multiples of 2^(-32). This implementation
will produce random reals down to 2^(-64) with the proper
frequencies. This makes it impossible to get a 0, which
avoids the rare, but irritating program-stopping situation
that arises from taking a logarithm of, or dividing by, zero.
VERSATILE
o Random bits, bytes, 16 or 32 bit integers with or without sign.
o Single or double precision real numbers signed or unsigned.
FAST
o We have aimed first for quality, and have sacrificed speed for
quality at every step. This can be seen in the implementation
of the single precision uni or vni, or in the intrand routines.
o Despite this, the speed of this method is only slightly slower
than an efficient implementation of the most common simple
congruential generator, and is faster than some implementations.
o The Subtract-with-Borrow (SWB) operation is part of almost
every machine architecture, but is not available to most high
level languages. Using assembler, the entire SWB operation
can be done in a single instrution.
o For those who are interested in pure speed, a FAST option
is available. This skips the mixing with a congruential
generator, providing just a simple SWB sequence. The period
is still extremely long, and the randomness properties should
satisfy all but the most demanding users.
o For those with 80386 or 80486 hardware which allows for 32-bit
multiplications, some 30% speedup is available by using the
32-bit versions, which exploit these instructions.
o Sample timings using Turbo-C++ 1.0 (small memory model) in
microseconds on a Gateway 486/33C PC were:
Full version (SWB+congruential)
dvni duni vni uni 32bit 31bit 16bit 15bit 8bit 7bit 1bit
32bit 7.51 7.66 5.28 5.30 3.18 3.25 1.91 1.91 1.39 1.39 1.46
plain 10.65 10.80 6.93 6.90 4.65 4.68 2.75 2.72 1.74 1.74 1.50
C 18.50 18.67 9.68 9.78 8.07 8.16 4.89 4.86 2.86 2.86 2.78
`FAST' version (no congruential)
dvni duni vni uni 32bit 31bit 16bit 15bit 8bit 7bit 1bit
32bit 4.82 5.03 3.88 3.84 1.82 1.76 1.23 1.23 1.07 1.07 1.47
plain 5.92 6.05 4.49 4.42 2.26 2.28 1.60 1.54 1.23 1.16 1.43
C 11.49 11.63 6.28 6.29 4.52 4.64 3.10 3.13 1.93 1.93 2.73
Timings (in microseconds) were obtained by timing a long loop,
hence they include the subroutine calling and looping times.
32bit - refers to the 80386/80486 ('X' version).
plain - is the plain assembler implementation.
C - is the ULTRA.C (entirely in Turbo C) implementation.
PORTABLE
o The entire generator is based around a random stream of 32bit
words, which can be generated a byte at a time (or even a bit
at a time). Since this same bit stream will be duplicated on any
architechture, the entire sequence of random numbers will be
the same, even for different architectures.
o Actually the outputs of i16bit, i15bit, i8bit, i7bit and i1bit
may be different depending on whether the machine is `big-endian'
or `little-endian'. On the other hand, the i32bit and i31bit
as well as uni, vni, duni and dvni should not be affected by
this. Even they byte routines could be made identical at the
cost of performance.
o It is essential to implement the algorithm in assembler in order
to gain its tremendous speed advantages. On the other hand
a C program (ultra.c) which is about half as fast as the assembler
has been provided to to aid understanding and debugging the
implementation on another machine.
o We would welcome any news about successful ports to other
architectures. To begin a port, first examine ultra.c. If
you understand PC assembler, it would also help to look at
ult32cod.asm.
The principal component of ULTRA is the Subtract-with-Borrow (SWB)
generator that is described in our paper `A New Class of Random Number
Generators', Annals of Applied Probability V1 462-480, 1991.
We use a 148 byte seed array, to obtain an astronomically large
period, while satisfying all the usual theoretical and experimental
tests for randomness.
The other component of ULTRA is the congruential generator with
multiplier 69069 and base 2^32. This is a very well known, reliable
(but short period) generator, tried and tested. It is, for example,
the generator built into VAX's.
The results of both of these generators are xor'ed to provide the
bytes which form the output of the ULTRA random number generator.
---------------------------------------------------------------------
COMPILATION INSTRUCTIONS
This assembler code is written for TASM 2.0, to allow one program
to serve for many different languages.
The header files define language dependent macros. These are:
ULTRA_C.ASM, ULTRA_TP.ASM and ULTRA_LH.ASM are for Turbo C,
Turbo Pascal and Lahey Fortran respectively.
All of these files then include the core files ULTRADAT.INC and
ULTRACOD.INC, which actually implement the algorithm.
A second set of files ULT32_C.ASM, ULT32_TP.ASM, and ULT32_LH.ASM
which include ULTRADAT.INC and ULT32COD.INC are the same programs
rewritten to use 32 bit code available on 80386 or 80486 machines
for faster execution.
The C files ULTRA_C.ASM and ULT32_C.ASM depend on the user defining
a variable `m' to be the memory model. Thus the command:
TASM -dm=small ULTRA_C.ASM
will create a small memory model object file. The memory model can
be any of `tiny', `small', `compact', `medium', `large' or `huge'.
Implementation in any other language which is not supported here
is simply a matter of fixing the header file.
----------------------------------------------------------------------
FUNCTIONS and SUBROUTINES
The i[n]bit functions
---------------------
i1bit, i7bit, i8bit, i15bit, i16bit, i31bit, i32bit
For n=32, 16, 8 these return a 4, 2, 1 byte answer which has
all bits random, hence is a random integer. If it is treated
as a signed integer, it ranges from -2^(n-1) to 2^(n-1)-1.
As an unsigned integer it range is 0 to 2^n-1.
For n=31, 15, 7 these return a 4, 2, 1 byte answer, but since
the sign bit is always off, these are always positive integers
from 0 and 2^n-1.
[d][u/v]ni functions
--------------------
uni() is a single precision uniform random number strictly
between 0 and 1. uni() always has 24 bits of precision;
it will never be 0 (or 1).
vni() is a single precision uniform between -1 and 1. It always has
24 bits of precision, and it never takes on the extreme values.
duni() and dvni() are double precision version of uni and vni.
They have no more than 64 bits of precision.
rinit(n1,n2)
------------
Calling rinit(n1,n2) initializes the seed array, using
the two 32-bit integer arguments n1 and n2.
The first argument should be odd (if it isn't it is made so).
If rinit is not called, the built-in default state is
what would result from the call rinit(1234567,7654321).
swbstate and swbsize
--------------------
In order to allow the user to save the state of the generator
so that it could take up from where it left off, the global variable
swbstate is an array containing swbsize bytes. Saving the entire
array will save the state of the generator. The eight bytes
following this array are insensitive to being changed, so if
a few more bytes are restored because the language only allows
integer arrays, there should be no problem. Thus you can always
save/restore 4 + 4*(swbsize div 4) bytes, if you need to.
Currently swbsize is 653 bytes.
----------------------------------------------------------------------
ADDING ANOTHER LANGUAGE
The Header files are where all language-dependent entry and exit
conventions have been placed. If you want to add another language
which uses another protocol to pass arguments, return values, or
save registers, this is where you want to modify the program.
You must define:
EnterProcedure:
Save registers etc.
Make DS point to the data segement if it doesn't.
ExitProcedure:
Restore registers and execute a ret.
Enter2arg:
Save registers etc.
Make ES and DS point to the data segment.
in Ultra: Load the two arguments for RINIT into CONGX and SHRGX.
in Ult32: Load the two arguments into EAX and EBX.
Exit2arg: Restore registers and execute a ret.
DwordFn The function result is in DX:AX. Place it
where the language expects it to be.
WordFn Put result from AX to where it is expected.
ByteFn Put result from AL to where it is expected.
RealFn,DoubleFn Put result from NDP stack to where it should be.
The segment names, classes etc must also be defined here.
the files ULTRADAT.INC and ULTRACOD.INC (or ULT32DAT.INC
and ULT32COD.INC) must be included in the appropriate
segments. Look at examples of header files for more information.